package leetcode;

import java.util.*;

public class Code30_1 {
    public static void main(String[] args) {
        List<Integer> list = new Code30_1().findSubstring("wordgoodgoodgoodbestword",
                new String[]{"word","good","best","good"});

        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
        System.out.println();
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        if (s.length() == 0 || words.length == 0) {
            return list;
        }
        HashMap<String, Integer> stringToNumber = new HashMap<>();
        HashMap<String, Integer> stringToIndex = new HashMap<>();
        for (int a = 0,b=0; a < words.length; a++) {
            stringToNumber.put(words[a], stringToNumber.getOrDefault(words[a], 0) + 1);
            if (!stringToIndex.containsKey(words[a])) {
                stringToIndex.put(words[a], b);
                b++;
            }
        }
        int wordLength = words[0].length();
        int[] b = new int[stringToNumber.size()];
        for (int a = wordLength * words.length - 1; a < s.length(); a++) {
            String s1 = s.substring(a - wordLength + 1, a + 1);
            if (stringToIndex.get(s1) != null) {
                Arrays.fill(b, Integer.MIN_VALUE);
                b[stringToIndex.get(s1)] = b[stringToIndex.get(s1)] == Integer.MIN_VALUE ? stringToNumber.get(s1)  : b[stringToIndex.get(s1)];
                int index = a - wordLength;
                int length = 1;
                b[stringToIndex.get(s1)]--;
                while (index - wordLength + 1 >= 0) {
                    String s2 = s.substring(index - wordLength + 1, index + 1);
                    if (stringToIndex.get(s2) != null) {
                        b[stringToIndex.get(s2)] = b[stringToIndex.get(s2)] ==Integer.MIN_VALUE ? stringToNumber.get(s2) : b[stringToIndex.get(s2)];
                        if (b[stringToIndex.get(s2)] > 0) {
                            length++;
                            index = index - wordLength;
                            b[stringToIndex.get(s2)]--;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if (length == words.length) {
                    list.add(index + 1);
                }
            }
        }
        return list;
    }
}
